/*
 *  Force Directed Graph JavaScript framework, version 12.05.12
 *
 *  Based on the Graph JavaScript framework, version 0.0.1
 *  (c) 2006 Aslak Hellesoy <aslak.hellesoy@gmail.com>
 *  (c) 2006 Dave Hoover <dave.hoover@gmail.com>
 *
 *  Ported from Graph::Layouter::Spring in
 *    http://search.cpan.org/~pasky/Graph-Layderer-0.02/
 *  The algorithm is based on a spring-style layouter of a Java-based social
 *  network tracker PieSpy written by Paul Mutton E<lt>paul@jibble.orgE<gt>.
 *
 *  Force Directd Graph JavaScript is freely distributable under the terms
 *  of an MIT-style license.
 *  
Copyright (c) 2012 Michael Brewer <michael.keith.brewer@gmail.com>

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
/*--------------------------------------------------------------------------*/

var Graph = Graph || {};
 
/*
*
* @namespace Graph
* @class SpringGraph
*/
Graph.SpringGraph = (function (global) {
	// dependencies
	// private properties
	// private methods
    var Constructor;
	// end var
	
    // one-time init procedures
    // ...
    // public API -- constructor
    /*
    * Constructs SpringGraph objects
    * @class SpringGraph
    * @constructor
    * @param {Object} canvas The HTML5 canvas element to draw onto
    */
	Constructor = function (canvas)
	{

		if (!(this instanceof Graph.SpringGraph))
		{ // ensure proper constructor use.
			return new Graph.SpringGraph(canvas);
		}

	    /*
		* Scales the abstract node positions into positions on the canvas
		* @param {Object} point The point to convert into canvas coordinates
		*/
		var translate = function(point)
		{
			return [
				(point[0] - this.layoutMinX) * this.factorX + this.radius,
				(point[1] - this.layoutMinY) * this.factorY + this.radius
			];
		};

		/*
		* Rotates about a point at some given length and angle
		* @param {Object} point The origin point
		* @param {Number} length Distance from the point
		* @param {Number} angle Angle to rotate to, in global coordinate space
		*/
		var rotate = function(point, length, angle)
		{
			var dx = length * Math.cos(angle);
			var dy = length * Math.sin(angle);
			return [point[0]+dx, point[1]+dy];
		};

		/*
		* Draws a single node onto the canvas and moves the associated DOM element to the correct position.
		* @param {Number} angle Angle to rotate to, in global coordinate space
		*/
		var drawNode = function(node)
		{
			var point = translate.call(this, [node.layoutPosX, node.layoutPosY]);

			node.value.style.position = 'absolute';
			node.value.style.top      = point[1] + 'px';
			node.value.style.left     = point[0] + 'px';

			this.ctx.strokeStyle = 'black';
			this.ctx.beginPath();
			this.ctx.arc(point[0], point[1], this.radius, 0, Math.PI*2, true);
			this.ctx.closePath();
			this.ctx.stroke();
		};

		/*
		* Draws a single edge onto the canvas and moves the associated DOM elements to the correct positions.
		* @param {Number} angle Angle to rotate to, in global coordinate space
		*/
		var drawEdge = function(edge)
		{
			var source = translate.call(this, [edge.source.layoutPosX, edge.source.layoutPosY]);
			var target = translate.call(this, [edge.target.layoutPosX, edge.target.layoutPosY]);

			var tan = (target[1] - source[1]) / (target[0] - source[0]);
			var theta = Math.atan(tan);
			if(source[0] <= target[0]) {theta = Math.PI+theta}
			source = rotate.call(this, source, -this.radius, theta);
			target = rotate.call(this, target, this.radius, theta);

			// draw the edge
			this.ctx.strokeStyle = 'grey';
			this.ctx.fillStyle = 'grey';
			this.ctx.lineWidth = 1.0;
			this.ctx.beginPath();
			this.ctx.moveTo(source[0], source[1]);
			this.ctx.lineTo(target[0], target[1]);
			this.ctx.stroke();

			drawArrowHead.call(this, 20, this.arrowAngle, theta, source[0], source[1], target[0], target[1]);
		};

		/*
		* Draws an arrow head onto the child end of an edge.
		*/
		var drawArrowHead = function(length, alpha, theta, startx, starty, endx, endy) {
				var top = rotate([endx, endy], length, theta + alpha);
				var bottom = rotate([endx, endy], length, theta - alpha);
				this.ctx.beginPath();
				this.ctx.moveTo(endx, endy);
				this.ctx.lineTo(top[0], top[1]);
				this.ctx.lineTo(bottom[0], bottom[1]);
				this.ctx.fill();
		}
		
		var calcBounds = function()
		{
			var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;

			for (var i = 0; i < this.nodes.length; i++)
			{
				var x = this.nodes[i].layoutPosX;
				var y = this.nodes[i].layoutPosY;
								   
				if(x > maxx) maxx = x;
				if(x < minx) minx = x;
				if(y > maxy) maxy = y;
				if(y < miny) miny = y;
			}

			this.layoutMinX = minx;
			this.layoutMaxX = maxx;
			this.layoutMinY = miny;
			this.layoutMaxY = maxy;
        }
		
		var layoutIteration = function()
		{
			// Forces on nodes due to node-node repulsions
			for (var i = 0; i < this.nodes.length; i++)
			{
				var node1 = this.nodes[i];
				for (var j = i + 1; j < this.nodes.length; j++)
				{
					var node2 = this.nodes[j];
					layoutRepulsive.call(this,node1, node2);
				}
			}
			// Forces on nodes due to edge attractions
			for (var i = 0; i < this.edges.length; i++)
			{
				var edge = this.edges[i];
				layoutAttractive.call(this,edge);
			}
			   
			// Move by the given force
			for (var i = 0; i < this.nodes.length; i++)
			{
				var node = this.nodes[i];
				var xmove = this.c * node.layoutForceX;
				var ymove = this.c * node.layoutForceY;

				var max = this.maxVertexMovement;
				if(xmove > max) xmove = max;
				if(xmove < -max) xmove = -max;
				if(ymove > max) ymove = max;
				if(ymove < -max) ymove = -max;

				node.layoutPosX += xmove;				
				node.layoutPosY += ymove;
				
				node.layoutForceX = 0;
				node.layoutForceY = 0;
			}
		};

		layoutRepulsive = function(node1, node2)
		{
			var dx = node2.layoutPosX - node1.layoutPosX;
			var dy = node2.layoutPosY - node1.layoutPosY;
			var d2 = dx * dx + dy * dy;
			if(d2 < 0.01)
			{
				dx = 0.1 * Math.random() + 0.1;
				dy = 0.1 * Math.random() + 0.1;
				var d2 = dx * dx + dy * dy;
			}
			var d = Math.sqrt(d2);
			if(d < this.maxRepulsiveForceDistance)
			{
				var repulsiveForce = this.k2 / d;
				node2.layoutForceX += repulsiveForce * dx / d;
				node2.layoutForceY += repulsiveForce * dy / d;
				node1.layoutForceX -= repulsiveForce * dx / d;
				node1.layoutForceY -= repulsiveForce * dy / d;
			}
        };

		layoutAttractive = function(edge)
		{
			var node1 = edge.source;
			var node2 = edge.target;

			var dx = node2.layoutPosX - node1.layoutPosX;
			var dy = node2.layoutPosY - node1.layoutPosY;
			var d2 = dx * dx + dy * dy;
			if(d2 < 0.01)
			{
				dx = 0.1 * Math.random() + 0.1;
				dy = 0.1 * Math.random() + 0.1;
				var d2 = dx * dx + dy * dy;
			}
			var d = Math.sqrt(d2);
			if(d > this.maxRepulsiveForceDistance)
			{
				d = this.maxRepulsiveForceDistance;
				d2 = d * d;
			}
			var attractiveForce = (d2 - this.k2) / this.k;
			if(edge.weight == undefined || edge.weight < 1) edge.weight = 1;
			attractiveForce *= Math.log(edge.weight) * 0.5 + 1;

			node2.layoutForceX -= attractiveForce * dx / d;
			node2.layoutForceY -= attractiveForce * dy / d;
			node1.layoutForceX += attractiveForce * dx / d;
			node1.layoutForceY += attractiveForce * dy / d;
        };
		
		this.nodeSet = {};
		this.nodes = [];
		this.edges = [];
		this.canvas = canvas;
		this.ctx = canvas.getContext("2d");
		this.radius = 20;	// node radius
		this.arrowAngle = Math.PI/10;
		this.maxRepulsiveForceDistance = 6;
		this.k = 2; // Mass
		this.k2 = this.k * this.k;
		this.c = 0.01; // Speed
		this.maxVertexMovement = 0.5;
		
		//Privelaged Methods
		/*
		* Draws all nodes and edges onto the canvas. The canvas will be cleared before drawing objects.
		*/
		this.draw = function()
		{
			calcBounds.call(this);
			this.factorX = (this.canvas.width - 2 * this.radius - 2) / (this.layoutMaxX - this.layoutMinX);
			this.factorY = (this.canvas.height - 2 * this.radius - 2) / (this.layoutMaxY - this.layoutMinY);
			this.canvas.width = this.canvas.width; // wipe the canvas
			for (var i = 0; i < this.nodes.length; i++)
			{
				drawNode.call(this, this.nodes[i]);
			}
			for (var i = 0; i < this.edges.length; i++)
			{
				drawEdge.call(this, this.edges[i]);
			}
		};
		
		/*
		* Processes one step in the graph's layout, causing nodes to adjust to the attractive and repulsive forces acting on them.
		*/
		this.step = function()
		{
			layoutIteration.call(this);
		};
    };
	
    // public API -- prototype
    Constructor.prototype = 
	{
		constructor: Graph.SpringGraph,
	    /*
		* Adds a new node to the SpringGraph's collection
		* @param {Object} value Either a string givnig the unique ID and Value 
		*					for a new div object, or an existing div object
		*					with a defined id
		*/
		addNode: function(value)
		{
			var node, key, value;
			if(typeof value === 'string')
			{
				// String value provided. Need to find the existing div or create a new div
				key = value;
				node = this.nodeSet[key];
				if(typeof node === 'undefined')
				{
					var element = global.document.createElement('div');
					element.innerHTML = value;
					global.document.body.appendChild(element);
					node = new Graph.SpringGraph.Node(element);
					this.nodeSet[key] = node;
					this.nodes.push(node);
				}
			} else
			{
				// Assuming it's a DOM node *with* an id.
				key = value.id;
				element = value;
				node = this.nodeSet[key];
				if(typeof node === undefined)
				{ // Node does not exist, add the new node.
					node = new Graph.SpringGraph.Node(element);
					this.nodeSet[key] = node;
					this.nodes.push(node);
				}
			}
			return node;
        },

	    /*
		* Adds a new edge between two nodes to the SpringGraph's collection
		* @param {Object} source The parent in the edge's relationship.
		*					Either a string givnig the unique ID and Value 
		*					for a new div object, or an existing div object
		*					with a defined id
		* @param {Object} target The child in the edge's relationship.
		*					Either a string givnig the unique ID and Value 
		*					for a new div object, or an existing div object
		*					with a defined id
		*/
        addEdge: function(source, target)
		{
			var s = this.addNode(source);
			var t = this.addNode(target);
			var edge = {source: s, target: t};
			this.edges.push(edge);
        }
	};
    // return the constructor to be assigned to the new namespace
    return Constructor;
}(this));

/*
*
* @namespace Graph.SpringGraph
* @class Node
*/
Graph.SpringGraph.Node = (function (global) {
	// dependencies
	// private properties
	// private methods
    var    Constructor;
	// end var
	
    // one-time init procedures
    // ...
    // public API -- constructor
    /*
    * Constructs Node objects
    * @class Node
    * @constructor
    * @param {String} value The display contents of the node
    */
	Constructor = function (value)
	{

		if (!(this instanceof Graph.SpringGraph.Node))
		{ // ensure proper constructor use.
			return new Graph.SpringGraph.Node(value);
		}

		this.value = value;
		this.layoutPosX = 0;
		this.layoutPosY = 0;
		this.layoutForceX = 0;
		this.layoutForceY = 0;
    };
    Constructor.prototype = 
	{
		constructor: Graph.SpringGraph.Node
	}
	
	return Constructor;
}());